|
In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also ''random walk'' for more general treatment of this topic. ==Definition== Assume ''G'' is some graph and is some path of length ''n'' on ''G''. In other words, are vertices of ''G'' such that and are connected by an edge. Then the loop erasure of is a new simple path created by erasing all the loops of in chronological order. Formally, we define indices inductively using : : where "max" here means up to the length of the path . The induction stops when for some we have . Assume this happens at ''J'' i.e. is the last . Then the loop erasure of , denoted by is a simple path of length ''J'' defined by : Now let ''G'' be some graph, let ''v'' be a vertex of ''G'', and let ''R'' be a random walk on ''G'' starting from ''v''. Let ''T'' be some stopping time for ''R''. Then the loop-erased random walk until time ''T'' is LE(''R''(())). In other words, take ''R'' from its beginning until ''T'' — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path. The stopping time ''T'' may be fixed, i.e. one may perform ''n'' steps and then loop-erase. However, it is usually more natural to take ''T'' to be the hitting time in some set. For example, let ''G'' be the graph Z2 and let ''R'' be a random walk starting from the point (0,0). Let ''T'' be the time when ''R'' first hits the circle of radius 100 (we mean here of course a ''discretized'' circle). LE(''R'') is called the loop-erased random walk starting at (0,0) and stopped at the circle. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Loop-erased random walk」の詳細全文を読む スポンサード リンク
|